This invention relates to wireless data networks and more particularly to a multiple-hop wireless radio frequency mesh network routing scheme employing a packet switched communications protocol. This invention has particular application to data collection from an array of sensors disposed in a topology wherein at least two intelligent communication nodes are within reliable radio communication range within a matrix of peer communication nodes.
Wireless mesh networks employ intelligent nodes comprising a transmitter and receiver, a power source, input devices, sometimes output devices, and an intelligent controller, such as a programmable microprocessor controller with memory. In the past, wireless mesh networks have been developed having configurations or networks for communication that are static, dynamic or a hybrid of static and dynamic.
A self-contained unit of communication information is called a packet. A packet has a header, a payload and an optional trailer. A link is a path which originates at exactly one node and terminates at exactly one other node. A node is thus any vertex or intersection in a communication network. A node may be passive or intelligent. In the present invention, a node is assumed to be intelligent in that it is capable of receiving and analyzing information, taking certain actions as a result of received information, including the storing of received or processed information, modifying at least part of received information, and in some instances originating and retransmitting information.
A circuit switched network is a communication network in which a fixed route is established and reserved for communication traffic between an origin and an ultimate destination. A packet-switched network is a communication network in which there is no reserved path between an origin and a destination such that self-contained units of communication traffic called packets may traverse a variety of different sets of links between the origin and the destination during the course of a message.
Circuit-switched networks are susceptible to node or link failure along a circuit path. For a telephone system with central ownership of the hardware, susceptibility to occasional failure was acceptable, as reliability on nodes and links was very high due to central ownership of the hardware. The ARPA net, a packet-switched network, was created to provide a mechanism for large area multi-hop communication when link and node reliability was reduced as for example due to the interconnection of many networks controlled or owned by different organizations. Asynchronous Transfer Mode (ATM) networks provide virtual circuits through central offices in conjunction with a packet-switched network and thus have both packet switched and circuit switched network characteristics.
ATM adapts circuit switched systems to support packet communications. ATM stands for Asynchronous Transfer Mode and refers to a specific standard for a cell switching network with a bandwidth from 25 Mbps to 622 Mbps. In ATM systems, a cell is a fixed-length data packet that flows along a pre-defined virtual circuit in a multi-hop network. Each node in the network through which the cell flows has a table which maps the virtual circuit to a next-hop on the cell's route. The speed of switching is enhanced by rapid examination of routing information in packet headers.
In all of these systems, link reliability is dramatically higher than in a typical wireless sensor network. Even in a packet switched network with unreliable links, it is still expected that the mean time between failure for a link is very large compared to the mean time between packets. Thousands, millions, or even billions of packets are expected to be delivered over a link, on average, before it would be expected to fail. (Packet error rates are typically measured in terms of the number of nines of reliability—for example 99.999% successfully delivered is five nines.) In this environment, it is perfectly reasonable to build large routing tables at nodes in the network and to change them infrequently.
In wireless sensor networks, such assumptions about link failure and packet error rate cannot be made. Due to the low power constraints, harsh RF communication environment, and dynamic nature of many sensor network deployments, link failures are common, and packet error rates are high. Link failures every ten packets, and packet error rates of 50% are not uncommon in the academic literature.
Conventional multi-hop routing is designed for the demands of the Internet and of telephone networks. Any node may at any time need to send information to any other node in the network. This is not the case with wireless sensor networks, since there are generally regular patterns of data flow in the network, and the desired flows are changed infrequently.
The wireless sensor network environment requires a new kind of packet routing. The challenge is to provide a mechanism to support the regular flow of data over a collection of presumably unreliable links.
The virtual circuit in an ATM system is like a fluid pipeline: it starts in one place and ends in another and may zigzag as it goes through various pumping stations, but topologically it is a continuous straight line. The paradigm of the Internet is packet switched network. A packet switched network is analogous to an airline: in principle one could fly from coast to coast via various routes through any number of different cities, but booking with a particular airline results in a flight route through a particular node or hub city, such as Chicago. If you get to Chicago and the plane originally scheduled to fly to the ultimate destination, such as New York, is out of service, it is normally necessary to re-book the remainder of the flight route via a different plane or intersecting airline service.
Also well known in the art are various packet based protocols, such as AX.25, both of which typically employ in part source routing, namely explicit routing between source and destination in a packet switched model. These have been described in various readily available standards.
In order to further understand the background of the invention, it is helpful to understand a number of related concepts. Referring to FIG. 1A, a graph is defined as a collection of vertices or nodes with connections, or links, between the nodes. Referring to FIG. 1B, a digraph is defined as a graph where all of the links have an associated direction, so that a digraph connects a plurality of nodes in a network with links defining direction of flow. Referring to FIG. 1C, a multi-digraph is defined as a digraph in which there exists at least one pair of links which both originate at the same originating node and terminate on the same terminating node. It is possible to have multiple multi-digraphs, if there is a first multi-digraph in which each link is labeled “1”, and a second multi-digraph in which each link is labeled “2”, and one or more of the nodes in the first graph is also in the second graph, then this is an example of multiple multi-digraphs.
Herein the concept of digraph-based packet transport is introduced. Digraph based packet transport is analogous to water flowing in a river delta with its meandering branches. If a number of intelligent entities each in an independent unpropelled watercraft were dropped all over the delta with no means of guidance except to choose a path at each fork, they would take a wide variety of paths, depending on flow and congestion. Eventually, all would arrive at the basin. Two that started far apart might end up close together, and two that started near each other might take completely different paths and arrive at different times.
A number of patents and publications provide background on other approaches to packet communication. Examples of instructive patents include: U.S. Pat. Nos. 4,550,397; 4,947,388; 4,939,726; 5,007,752; 5,079,768; 5,115,433; 5,130,987; 5,471,469; 5,488,608; 5,515,369; 5,570,084; 5,903,566; 6735178.